package algorithm.difficult;

import pojo.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class MergeKLists23 {

    public static void main(String[] args) {
        //[[1,5,7],[2,4,6],[3,9]]
        ListNode[] lists = new ListNode[3];
        lists[0] = new ListNode(1);
        lists[0].next = new ListNode(5);
        lists[0].next.next = new ListNode(7);
        lists[1] = new ListNode(2);
        lists[1].next = new ListNode(4);
        lists[1].next.next = new ListNode(6);
        lists[2] = new ListNode(3);
        lists[2].next = new ListNode(9);
        System.out.println(mergeKLists(lists));
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode head = null;
        ListNode pre = new ListNode();
        while (true) {
            boolean flag = false;
            int index = 0;
            ListNode min = null;
            for (int i = 0; i < lists.length; i++) {
                ListNode node = lists[i];
                if (node == null) {
                    continue;
                }
                if (min == null) {
                    min = node;
                }
                if (node.val <= min.val) {
                    min = node;
                    index = i;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }

            //更新min处
            lists[index] = min.next;
            pre.next = min;
            pre = min;
            if (head == null) {
                head = min;
                pre = head;
            }
        }
        return head;
    }

}
